<!DOCTYPE html>
<html lang="zh-cn">

    <head>
        <meta charset="utf-8" />
        <title>StringMatcher</title>
        <style></style>
    </head>

    <body>
        <div style="width: 90%;margin: auto">
            选择算法：
            <select id="algorithm">
                <option value="1">Boyer–Moore</option>
                <option value="2">KMP</option>
            </select>
            <br> 样本串: <textarea id="sample" rows="5" cols="" style="width: 100%"></textarea>
            <br> 模式串: <textarea id="pattern" rows="4" cols="" style="width: 100%"></textarea>
            <br>
            <button onclick="find();">开始匹配</button>
            <br><span id="des"></span>
            <hr>
        </div>

        <script type="text/javascript">
            var matched = 0;

            function find() {
                var sep = document.getElementById("algorithm"),
                    s = document.getElementById("sample"),
                    p = document.getElementById("pattern"),
                    sv = s.value,
                    pv = p.value;

                console.log(KMP(sv, pv))
            }

            //BM算法入口
            function BMfunc(sString, pString) {
                var sarr = sString.split(''),
                    parr = pString.split('');
                var sindex = parr.length - 1; //起始待匹配位置
                var i = parr.length - 1; //从模式串尾部开始匹配测试
                for(; i >= 0; i--) {
                    if(parr[i] == sarr[sindex]) { //匹配成功，继续匹配前一个字符
                        sindex--;
                    } else {
                        sindex =
                            i = parr.length - 1;
                    }
                }
                if(i == -1) { //循环结束，模式串匹配完成
                    matched = sindex + 1;
                    return sindex;
                } else {
                    return false;
                }
            }

            /* P为模式串，下标从0开始 */
            function GetNext(P) {
                var p_len = P.length;
                var i = 0; //P的下标
                var j = -1;
                var next = [];
                next[0] = -1;

                while(i < p_len) {
                    if(j == -1 || P[i] == P[j]) {
                        i++;
                        j++;
                        next[i] = j;
                    } else
                        j = next[j];
                }
                return next;
            }

            /* 在S中找到P第一次出现的位置 */
            function KMP(S, P) {
                var next = GetNext(P);

                var i = 0; //S的下标
                var j = 0; //P的下标
                var s_len = S.length;
                var p_len = P.length;

                while(i < s_len && j < p_len) {
                    if(j == -1 || S[i] == P[j]) //P的第一个字符不匹配或S[i] == P[j]
                    {
                        i++;
                        j++;
                    } else
                        j = next[j]; //当前字符匹配失败，进行跳转
                }

                if(j == p_len) //匹配成功
                    return i - j;

                return -1;
            }
        </script>
    </body>

</html>